package com.heima.leetcode.practice;

/**
 * leetcode 69. x 的平方根
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/13 22:35
 */
public class E69 {
    /*
      1-99
      1-49
      1-24
      1-11
      7-11
     10-11
     10-9
     */

    // 二分查找每次范围都会缩小一半，最终都会缩小到一个元素范围的情况，这时left == right
    // 此时有三种情况，1、是目标值，返回；2、小于目标值，退出循环，left会加一，right不变
    // 3、大于目标值，退出循环，left不变，right会减一，这个时候二分查找最后要返回用到哪个指针
    // 这关系到二分查找中最后一个元素的业务意义，以这个为突破口

    // 在这个代码中二分查找的最后一轮，查找的是最接近目标值（只考虑小数情况，其它能找到）的数，
    // 肯定会有一个状态：begin = i， end = i + 1的情况，目标值理论就应该在begin和end之间
    // 中值就是begin，这样begin = end = i进入最后一轮，所以begin在左边，begin最终会自增一
    // 然后退出循环

    /**
     * 二分查找实现
     * @param x 目标值
     * @return 平方根整数部分
     */
    public int mySqrt(int x) {
        int begin = 1;
        int end = x;
        while (begin <= end){
            int median = (begin + end) >>> 1;
            long power = (long) median * median;
            if (power < x){
                begin = median + 1;
            } else if (power == x) {
                return median;
            } else {
                end = median - 1;
            }
        }
        return begin - 1; // 返回end也是一样的，这种类似的都是看end = begin+1的时候，期望值如果不存在在数组中，那么就在这俩中间
    }
}
